The present invention relates to the fabrication of integrated circuits, and more particularly to programmable logic devices.
Programmable logic devices (PLDs) are general-purpose integrated circuits that include both user-configurable circuitry and a configuration memory array that stores user-generated configuration data. The user-configurable circuitry typically includes logic elements and associated interconnect resources that are connected to the memory cells of the configuration memory array, and are programmed (configured) by the configuration data stored in the configuration memory array to implement user-defined Logic operations (that is, a user""s circuit). Examples of PLDs include field programmable gate arrays (FPGAs), such as the Virtex(trademark) family of FPGAs produced by Xilinx, Inc. of San Jose, Calif., and complex programmable logic devices (CPLDs), such as the XC9500 family of CPLDs produced by Xilinx, Inc.
FIG. 1 shows a portion of a field programmable gate array (FPGA) 100, which is one type of PLD. Although greatly simplified, FPGA 100 is generally consistent with FPGAs produced by Xilinx, Inc. of San Jose, Calif. FPGA 100 includes an array of configurable logic blocks (CLBs), input/output blocks (IOBs), and programmable interconnect resources that include interconnect lines 110 extending between the CLBs and IOBs. Each CLB includes a look-up table (LUT) and optional output registers (e.g., flip-flops), and conductive wires that extend from the CLB for selective connection to the interconnect lines. Each interconnect line 110 includes a series of wiring segments that are programmably coupled at their respective ends via programmable multi-way segment-to-segment switches (indicated by diamond shapes). In addition, vertical wiring segments are connectable to the conductive wires of associated CLBs via segment-to-CLB input switches, and output signals from each CLB are transmitted to a horizontal wiring segment via CLB-to-segment output switches (also indicated by diamond shapes).
During operation of FPGA 100, each CLB generates a single output signal in response to device input signals (i.e., received on designated device pins) and/or data signals generated by other CLBs of FPGA 100. In particular, in accordance with the configuration data stored in the configuration memory array (not shown) of FPGA 100, device input signals are routed from selected device pins through associated IOBs to the interconnect resources, which are linked by programmable switches to pass the data signals to selected CLBs. Upon entering a CLB, subsets of these input signals are used to address a single data value stored in the memory cells of the LUT. As is understood in the art, LUTs are programmed to implement any logic function of the subset of input signals by storing appropriate data signals in the memory cells of the LUT. The subset of input signals address the appropriate memory cell, and the data value associated with the logic function is generated at the output terminal of the CLB. Data signals output from the various CLBs are either passed to other CLBs, or are passed to selected IOBs for transmission onto a device pin.
An advantage of FPGAs is that the LUT of each CLB can perform any logic function having a few input terms. However, a problem associated with LUT-based FPGAs is that it is difficult to implement wide logic functions using a single LUT. Consequently, several CLBs must be used to implement a wide logic function. Although it is possible to efficiently utilize FPGA resources to connect the necessary CLBs in order to implement a wide logic function, the timing associated with the actual configuration is difficult to predict, and propagation delays increase with each additional CLB through which data signals must pass.
FIG. 2 is a simplified diagram showing a complex programmable logic device (CPLD) 200 that is disclosed in U.S. Pat. No. 5,714,890. CPLD 200 includes dual polarity input lines 201, a programmable AND array 210, a programmable OR array 220, a fixed OR array 230, and several macrocells 240. Programmable AND array 210 is divided into two groups of AND gates: a first group 212 whose output terminals are connected to programmable OR array 220, and a second group 215 whose output terminals are connected to fixed OR array 230. Each AND gate 213 of first group 212 has input terminals connected by programmable switches 214 (indicated by diamond shape) to selectively receive input signals from dual polarity input lines 201, and has an output terminal connected to programmable OR array 220. Similarly, each AND gate 216 of second group 215 has input terminals connected by programmable switches 217 to selectively receive input signals from dual polarity input lines 201, and has an output terminal connected to fixed OR array 230. Each OR gate 221 of programmable OR array 220 is connected by a programmable switch 223 to receive product-terms generated by first group 212 of AND array 210. Each OR gate 233 of fixed OR array 230 is connected to receive a sum-term generated by programmable OR array 220 and/or a product-term generated by second group 215 of AND array 210. Although indicated as an OR gate, each OR gate 233 of fixed OR array 230 can implement a NOR, XOR, or XNOR logic function. Finally, output signals from fixed OR array 230 are selectively transmitted back to programmable AND array 210 on feedback lines 235, or to macrocells 240 (indicated by tri-state buffers) for transmission onto one or more output pins (OP) of CPLD 200.
During operation of CPLD 200, in accordance with the configuration data stored in the configuration memory array (not shown) of CPLD 200, device input signals are routed from selected device input pins (IP) onto dual polarity lines 201, which transmit the input signals in inverted and non-inverted forms into programmable AND array 210. Selected AND gates 213 of first group 212 are programmably connected to receive selected input signals, and produce product-terms that are transmitted to programmable OR array 220. Selected AND gates 216 of second group 215 are programmably connected to receive selected input signals, and produce product-terms that are transmitted to fixed OR array 230. Finally, selected OR gates 221 of programmable OR array 220 are programmably connected to receive selected product-terms from first group 212, and generate sum-terms that are transmitted to fixed OR array 230. Fixed OR array 230 receives product-terms from second group 215 and sum-terms from OR array 220, and produces sum-of-products terms that are transmitted from fixed OR array 230 either back to AND array 210 on feedback lines 235, or to macrocells 240.
CPLD 200 has an advantage over FPGA 100 (discussed above) in that it is capable of implementing certain wide logic functions in a single pass. In particular, because multiple input signals can be combined in programmable AND array 210 and programmable OR array 220, CPLD 200 is capable of performing certain wide logic functions without requiring the use of feedback lines 235. However, unlike LUT-based FPGAs, it is difficult to implement certain complex logic functions in a single pass, often requiring partial solutions to be fed back into programmable AND array 210 on feedback lines 235 in order to implement these complex logic functions. This need to feed back partial solutions lowers resource utilization and greatly increases propagation delay through conventional CPLDs.
What is needed is a PLD structure that is able to implement both wide logic functions and complex logic functions in a single pass.
The present invention is directed to a programmable logic device (PLD) structure that combines the AND/OR structure of a conventional CPLD with the look-up table (LUT)-based logic structure of a field programmable gate array (FPGA) to implement both wide logic functions and complex logic functions in a single pass, thereby greatly reducing signal propagation delays by eliminating the need for multiple passes through the CPLD logic architecture.
In a first embodiment of the present invention, a CPLD includes a programmable AND array, a programmable OR array, and a look-up table (LUT) that is programmably connected to receive a product-term from the programmable AND array and connected to receive a sum-term from the programmable OR array. The programmable AND array is programmably connected to multiple input lines, and the programmable OR array is programmably connected to receive selected product-terms generated by the AND gates of the programmable AND array, thereby increasing the total input logic width of the LUT over that possible in a FPGA. Further, in comparison to conventional CPLDS, by replacing fixed function logic gates with the LUT, a substantially larger number of logic functions can be performed in a single pass through the CPLD of the present invention. Accordingly, not only does the present invention reduce chip resource usage over conventional FPGAs, but it also reduces signal propagation delay over conventional CPLDs by eliminating or reducing the need for multiple passes through the programmable AND array.
In accordance with a second embodiment of the present invention, the AND gates of the programmable AND array are separated into a first group whose product terms are transmitted to the programmable OR array, and a second group whose product terms are transmitted to the LUTs.
The present invention will be more fully understood in view of the following description and drawings.